/*
 * @lc app=leetcode.cn id=132 lang=typescript
 *
 * [132] 分割回文串 II
 */

// @lc code=start
function minCut(s: string): number {
  // 预处理，构建回文串的索引
  const extract = (s: string, i: number, j: number, index: number[][]) => {
    const n = s.length;
    while (i >= 0 && s[i] === s[j]) {
      index[j + 1].push(i);
      i--;
      j++;
    }
  };
  const n = s.length;
  // index[i] 表示以 s[i] 结尾的回文串的起始位置
  // index[3] = [1,2] 表示 [1,3)和[2,3)的区间都能构成回文串
  const index = new Array(n + 1).fill(0).map((_) => []);

  for (let i = 0; i < n; i++) {
    extract(s, i, i, index);
    extract(s, i, i + 1, index);
  }
  // dp[i]表示前i个字符有最少几个回文串
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    // 每个字符本身都是回文串
    dp[i] = i;
    for (const j of index[i]) {
      dp[i] = Math.min(dp[i], dp[j] + 1);
    }
  }

  // 要返回分割次数，所以需要减 1
  return dp[n] - 1;
}
// @lc code=end
